package woa.recursion;

import java.util.HashMap;
import java.util.Map;

/**
 * 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 注意：给定 n 是一个正整数。
 *
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 *
 * @author wangpeng
 * @date 2021/12/14
 */
public class ClimbStairs {

    static Map<Integer, Integer> memory = new HashMap<>();

    public static int climbStairs(int n) {
        if (n == 1 || n == 2) {
            return n;
        }

        if (memory.containsKey(n)) {
            return memory.get(n);
        }
        int rs = climbStairs(n - 1) + climbStairs(n - 2);
        memory.put(n, rs);
        return rs;
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(4));
    }
}
